package pri.zjy.tree;

import pri.zjy.tree.model.NTreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author zhangjy
 * @description  N 叉树的层序遍历
 * @date 2025/4/6 16 :49
 */
public class LevelOrder_429 {

    public static void main(String[] args) {

    }

    /**
     *  BFS-同二叉树层序遍历;
     *  <p>
     *  时间复杂度：O(n)；其中n是树中的节点个数，每个节点在BFS时只会被遍历一次。
     *  空间复杂度：O(n)；即为队列需要使用的空间。在最坏的情况下，树只有两层，且最后一层有 n−1 个节点，此时就需要 O(n) 的空间。
     */
    public List<List<Integer>> levelOrder(NTreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) return ans;

        Queue<NTreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            // 一次性把一层出完
            int curLayerCount = queue.size();
            List<Integer> curLayer = new ArrayList<>(curLayerCount);
            for (int i = 0; i < curLayerCount; i++) {
                NTreeNode poll = queue.poll();
                // 记录本层节点值
                curLayer.add(poll.val);

                // 所有子节点入队（非空入队）
                List<NTreeNode> children = poll.children;
                for (NTreeNode NTreeNode : children) {
                    if (NTreeNode != null) queue.offer(NTreeNode);
                }
            }
            ans.add(curLayer);
        }

        return ans;

    }


}
